import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    boolean visited[];
    boolean colored[];
    boolean color;
    boolean ok;
    public boolean isBipartite(int[][] graph) {
        int len = graph.length;
        visited = new boolean[len];
        colored = new boolean[len];
        color = false;
        ok = true;
        for(int i=0;i<len;i++){
            if(!visited[i]) DFS(graph,i,color);
        }
        return ok;
    }

    public void DFS(int[][] graph,int src,boolean color){
        if(!ok) return;
        //判断是否涂抹过
        visited[src] = true;
        colored[src] = color;
        int len = graph[src].length;
        for(int i=0;i<len;i++){
            if(graph[src][i]!=0){
                if(visited[i]!=true){
                    DFS(graph,i,!color);
                }else{
                    if(colored[i]==colored[src]){
                        ok = false;
                    }
                }
            }

        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isBipartite(new int[][]{{0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}}));
    }
}